/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.MergeableAddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable

/**
 * Fibonacci heaps. The heap is sorted according to the [ natural ordering][Comparable] of its keys, or by a [Comparator] provided at heap
 * creation time, depending on which constructor is used.
 *
 *
 *
 * This implementation provides amortized O(1) time for operations that do not
 * involve deleting an element such as `insert`, and `decreaseKey`.
 * Operation `findMin` is worst-case O(1). Operations `deleteMin`
 * and `delete` are amortized O(log(n)). The operation `meld` is
 * also amortized O(1).
 *
 *
 *
 * All the above bounds, however, assume that the user does not perform
 * cascading melds on heaps such as:
 *
 * <pre>
 * d.meld(e);
 * c.meld(d);
 * b.meld(c);
 * a.meld(b);
</pre> *
 *
 * The above scenario, although efficiently supported by using union-find with
 * path compression, invalidates the claimed bounds.
 *
 *
 *
 * Note that the ordering maintained by a Fibonacci heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `AddressableHeap` interface. (See `Comparable` or
 * `Comparator` for a precise definition of *consistent with
 * equals*.) This is so because the `AddressableHeap` interface is
 * defined in terms of the `equals` operation, but a Fibonacci heap
 * performs all key comparisons using its `compareTo` (or `compare`)
 * method, so two keys that are deemed equal by this method are, from the
 * standpoint of the Fibonacci heap, equal. The behavior of a heap *is*
 * well-defined even if its ordering is inconsistent with `equals`; it
 * just fails to obey the general contract of the `AddressableHeap`
 * interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
 *
 * @see PairingHeap
 *
 * @see CostlessMeldPairingHeap
</V></K> */
class FibonacciHeap<K, V> @ConstantTime constructor(
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    private val comparator: Comparator<in K?>?
) : MergeableAddressableHeap<K, V>,
    Serializable {

    /**
     * The root with the minimum key
     */
    private var minRoot: Node? = null

    /**
     * Number of roots in the root list
     */
    private var roots = 0

    /**
     * Size of the heap
     */
    private var size: Long

    /**
     * Auxiliary array for consolidation
     */
    private val aux: Array<Node?>

    /**
     * Used to reference the current heap or some other heap in case of melding,
     * so that handles remain valid even after a meld, without having to iterate
     * over them.
     *
     * In order to avoid maintaining a full-fledged union-find data structure,
     * we disallow a heap to be used in melding more than once. We use however,
     * path-compression in case of cascading melds, that it, a handle moves from
     * one heap to another and then another.
     */
    protected var other: FibonacciHeap<K, V>

    /**
     * Constructs a new, empty heap, using the natural ordering of its keys. All
     * keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     */
    @ConstantTime
    constructor() : this(null)

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    init {
        this.size = 0
        this.aux = java.lang.reflect.Array.newInstance(Node::class.java, AUX_CONSOLIDATE_ARRAY_SIZE) as Array<Node?>
        this.other = this
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalStateException
     * if the heap has already been used in the right hand side of a
     * meld
     */
    @ConstantTime(amortized = true)
    override fun insert(key: K, value: V?): Node {
        check(other === this) { "A heap cannot be used after a meld" }
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }
        val n = Node(this, key, value)
        addToRootList(n)
        size++
        return n
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalStateException
     * if the heap has already been used in the right hand side of a
     * meld
     */
    @ConstantTime(amortized = true)
    override fun insert(key: K): Node {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime(amortized = true)
    override fun findMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return minRoot!!
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        val z = minRoot!!

        // move z children into root list
        var x = z.child
        while (x != null) {
            val nextX = if ((x.next === x)) null else x.next

            // clear parent
            x.parent = null

            // remove from child list
            x.prev!!.next = x.next
            x.next!!.prev = x.prev

            // add to root list
            x.next = minRoot!!.next
            x.prev = minRoot
            minRoot!!.next = x
            x.next!!.prev = x
            roots++

            // advance
            x = nextX
        }
        z.degree = 0
        z.child = null

        // remove z from root list
        z.prev!!.next = z.next
        z.next!!.prev = z.prev
        roots--

        // decrease size
        size--

        // update minimum root
        if (z === z.next) {
            minRoot = null
        } else {
            minRoot = z.next
            consolidate()
        }

        // clear other fields
        z.next = null
        z.prev = null

        return z
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        /**
         * {@inheritDoc}
         */
        get() = size == 0L

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        minRoot = null
        roots = 0
        size = 0
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime(amortized = true)
    override fun meld(other: MergeableAddressableHeap<K, V>) {
        val h = other as FibonacciHeap<K, V>

        // check same comparator
        if (comparator != null) {
            require(!(h.comparator == null || h.comparator != comparator)) { "Cannot meld heaps using different comparators!" }
        } else require(h.comparator == null) { "Cannot meld heaps using different comparators!" }

        check(h.other === h) { "A heap cannot be used after a meld." }

        if (size == 0L) {
            // copy the other
            minRoot = h.minRoot
        } else if (h.size != 0L) {
            // concatenate root lists
            val h11 = minRoot
            val h12 = h11!!.next
            val h21 = h.minRoot
            val h22 = h21!!.next
            h11.next = h22
            h22!!.prev = h11
            h21.next = h12
            h12!!.prev = h21

            // find new minimum
            if ((comparator == null && (h.minRoot!!.key as Comparable<K?>?)!!.compareTo(
                    minRoot!!.key
                ) < 0)
                || (comparator != null && comparator.compare(h.minRoot!!.key, minRoot!!.key) < 0)
            ) {
                minRoot = h.minRoot
            }
        }
        roots += h.roots
        size += h.size

        // clear other
        h.size = 0
        h.minRoot = null
        h.roots = 0

        // take ownership
        h.other = this
    }

    // --------------------------------------------------------------------
    /** We maintain explicitly the belonging heap, instead of using an inner
         * class due to possible cascading melding.
         */
    inner class Node(var heap: FibonacciHeap<K, V>,
                              /**
                               * {@inheritDoc}
                               */
                              override var key: K,
                              /**
                               * {@inheritDoc}
                               */
                              override var value: V?
    ) : AddressableHeap.Handle<K, V>, Serializable {
        /**
         * {@inheritDoc}
         */
        var parent: Node? = null // parent
        var child: Node? = null // any child
        var next: Node? = null // younger sibling
        var prev: Node? = null // older sibling
        var degree: Int = 0 // number of children
        var mark: Boolean = false // marked or not

        /**
         * {@inheritDoc}
         */
        @ConstantTime(amortized = true)
        override fun decreaseKey(newKey: K) {
            val h = owner
            if (h.comparator == null) {
                h.decreaseKey(this, newKey)
            } else {
                h.decreaseKeyWithComparator(this, newKey)
            }
        }

        /**
         * {@inheritDoc}
         */
        @LogarithmicTime(amortized = true)
        override fun delete() {
            requireNotNull(this.next) { "Invalid handle!" }
            val h = owner
            h.forceDecreaseKeyToMinimum(this)
            h.deleteMin()
        }

        val owner: FibonacciHeap<K, V>
            /*
         * Get the owner heap of the handle. This is union-find with
         * path-compression between heaps.
         */
            get() {
                if (heap.other !== heap) {
                    // find root
                    var root = heap
                    while (root !== root.other) {
                        root = root.other
                    }
                    // path-compression
                    var cur = heap
                    while (cur.other !== root) {
                        val next = cur.other
                        cur.other = root
                        cur = next
                    }
                    heap = root
                }
                return heap
            }

    }

    /*
     * Decrease the key of a node.
     */
    private fun decreaseKey(n: Node, newKey: K) {
        val c = (newKey as Comparable<K?>).compareTo(n.key)
        require(c <= 0) { "Keys can only be decreased!" }
        n.key = newKey
        if (c == 0) {
            return
        }

        requireNotNull(n.next) { "Invalid handle!" }

        // if not root and heap order violation
        val y = n.parent
        if (y != null && (n.key as Comparable<K?>?)!!.compareTo(y.key) < 0) {
            cut(n, y)
            cascadingCut(y)
        }

        // update minimum root
        if ((n.key as Comparable<K?>?)!!.compareTo(minRoot!!.key) < 0) {
            minRoot = n
        }
    }

    /*
     * Decrease the key of a node.
     */
    private fun decreaseKeyWithComparator(n: Node, newKey: K) {
        val c = comparator!!.compare(newKey, n.key)
        require(c <= 0) { "Keys can only be decreased!" }
        n.key = newKey
        if (c == 0) {
            return
        }

        requireNotNull(n.next) { "Invalid handle!" }

        // if not root and heap order violation
        val y = n.parent
        if (y != null && comparator.compare(n.key, y.key) < 0) {
            cut(n, y)
            cascadingCut(y)
        }

        // update minimum root
        if (comparator.compare(n.key, minRoot!!.key) < 0) {
            minRoot = n
        }
    }

    /*
     * Decrease the key of a node to the minimum. Helper function for performing
     * a delete operation. Does not change the node's actual key, but behaves as
     * the key is the minimum key in the heap.
     */
    private fun forceDecreaseKeyToMinimum(n: Node) {
        // if not root
        val y = n.parent
        if (y != null) {
            cut(n, y)
            cascadingCut(y)
        }
        minRoot = n
    }

    /*
     * Consolidate: Make sure each root tree has a distinct degree.
     */
    private fun consolidate() {
        var maxDegree = -1

        // for each node in root list
        var numRoots = roots
        var x = minRoot
        while (numRoots > 0) {
            val nextX = x!!.next
            var d = x.degree

            while (true) {
                var y = aux[d] ?: break

                // make sure x's key is smaller
                var c = comparator?.compare(y.key, x!!.key) ?: (y.key as Comparable<K?>?)!!.compareTo(x!!.key)
                if (c < 0) {
                    val tmp = x!!
                    x = y
                    y = tmp
                }

                // make y a child of x
                link(y, x)

                aux[d] = null
                d++
            }

            // store result
            aux[d] = x

            // keep track of max degree
            if (d > maxDegree) {
                maxDegree = d
            }

            // advance
            x = nextX
            numRoots--
        }

        // recreate root list and find minimum root
        minRoot = null
        roots = 0
        for (i in 0..maxDegree) {
            if (aux[i] != null) {
                addToRootList(aux[i]!!)
                aux[i] = null
            }
        }
    }

    /*
     * Remove node y from the root list and make it a child of x. Degree of x
     * increases by 1 and y is unmarked if marked.
     */
    private fun link(y: Node?, x: Node?) {
        // remove from root list
        y!!.prev!!.next = y.next
        y.next!!.prev = y.prev

        // one less root
        roots--

        // clear if marked
        y.mark = false

        // hang as x's child
        x!!.degree++
        y.parent = x

        val child = x.child
        if (child == null) {
            x.child = y
            y.next = y
            y.prev = y
        } else {
            y.prev = child
            y.next = child.next
            child.next = y
            y.next!!.prev = y
        }
    }

    /*
     * Cut the link between x and its parent y making x a root.
     */
    private fun cut(x: Node, y: Node) {
        // remove x from child list of y
        x.prev!!.next = x.next
        x.next!!.prev = x.prev
        y.degree--
        if (y.degree == 0) {
            y.child = null
        } else if (y.child === x) {
            y.child = x.next
        }

        // add x to the root list
        x.parent = null
        addToRootList(x)

        // clear if marked
        x.mark = false
    }

    /*
     * Cascading cut until a root or an unmarked node is found.
     */
    private fun cascadingCut(y: Node) {
        var y = y
        var z: Node?
        while ((y.parent.also { z = it }) != null) {
            if (!y.mark) {
                y.mark = true
                break
            }
            cut(y, z!!)
            y = z!!
        }
    }

    /*
     * Add a node to the root list and update the minimum.
     */
    private fun addToRootList(n: Node) {
        if (minRoot == null) {
            n.next = n
            n.prev = n
            minRoot = n
            roots = 1
        } else {
            n.next = minRoot!!.next
            n.prev = minRoot
            minRoot!!.next!!.prev = n
            minRoot!!.next = n
            val c = comparator?.compare(n.key, minRoot!!.key) ?: (n.key as Comparable<K?>?)!!.compareTo(minRoot!!.key)
            if (c < 0) {
                minRoot = n
            }
            roots++
        }
    }

    companion object {
        private const val serialVersionUID: Long = 1

        /**
         * Size of consolidation auxiliary array. Computed for number of elements
         * equal to [Long.MAX_VALUE].
         */
        private const val AUX_CONSOLIDATE_ARRAY_SIZE = 91
    }
}
